#include <iostream>
#include <string.h>
#include <stack>
    /* 用栈来解决，检查栈顶元素 */
using namespace std;

class Solution 
{
public:
    bool isValid(string s) 
    {
        // 创建一个栈来保存左括号
        stack<char> st;

        for(char c : s)
        {
            // 如果是左括号，入栈
            if(c == '(' || c == '[' || c == '{')
            {
                st.push(c);
            }
            else
            {
                // 如果是右括号，检查栈顶是否有对应的左括号
                if(st.empty())
                {
                    return false;
                }
                char top = st.top();
                if((c == ')' && top != '(') ||
                   (c == ']' && top != '[') ||
                   (c == '}' && top != '{'))
                {
                    return false;
                }
                // 匹配成功，弹出栈顶元素
                st.pop();
            }
        }
        
        // 最后栈必须为空，如果还有未匹配的左括号则返回false
        return st.empty();
    }
};
int main()
{
    Solution sulo;
    string s = "([}}])";
    cout << sulo.isValid(s) << endl;



    return 0;
}